(ns btree.operations-test
	(:require [clojure.test :refer :all] [btree.operations :refer :all])
    (:import [com.google.gson Gson GsonBuilder])
)

(defn createTestTree
	"creates example tree for tests"
	[]
	(def ttree { :pageSize 2 :nextId 5 :root 1
		1 {:keys [10 100] :children [2 3 4] :parent nil} ;1
		2 {:keys [2 4 7] :children [] :parent 1} ;2
		3 {:keys [12 20 40 91] :children [] :parent 1} ;3
		4 {:keys [101 200] :children [] :parent 1} ;4
	})
	ttree
)

(defn createUnbalancedTestTree ;children in leafs added for test purposes (it's not a valid tree because of them!)
	"creates example tree for tests"
	[]
	(def ttree { :pageSize 2 :nextId 5 :root 1
		1 {:keys [10 100] :children [2 3 4] :parent nil} ;1
		2 {:keys [2 4 7] :children [101 102 103 104] :parent 1} ;2
		3 {:keys [12 20 40 91 99] :children [111 112 113 114 115 116] :parent 1} ;3 - overflowed
		4 {:keys [101 ] :children [120 121] :parent 1} ;4 - underflowed
	})
	ttree
)

(defn createUnbalancedTestTreeWithFullRightSibling
	"creates example tree for tests"
	[]
	(def ttree { :pageSize 2 :nextId 5 :root 1
		1 {:keys [10 100] :children [2 3 4] :parent nil} ;1
		2 {:keys [2 4 7] :children [101 102 103 104] :parent 1} ;2
		3 {:keys [12 20 40 91 99] :children [111 112 113 114 115 116] :parent 1} ;3 - overflowed
		4 {:keys [101 107 128 300] :children [120 121 122 123 124 125] :parent 1} ;4 - full
	})
	ttree
)

(defn createUnbalancedTestTreeWithFullOnlySibling
	"creates example tree for tests"
	[]
	(def ttree { :pageSize 2 :nextId 5 :root 1
		1 {:keys [10 100] :children [2 3 4] :parent nil} ;1
		2 {:keys [2 4 7] :children [] :parent 1} ;2
		3 {:keys [12 20 40 91] :children [] :parent 1} ;3 - overflowed
		4 {:keys [101 107 128 300 701] :children [] :parent 1} ;4 - full
	})
	ttree
)

(defn createUnbalancedTestTreeWithFullBothSiblings
	"creates example tree for tests"
	[]
	(def ttree { :pageSize 2 :nextId 5 :root 1
		1 {:keys [10 100] :children [2 3 4] :parent nil} ;1
		2 {:keys [2 4 7 9] :children [101 102 103 104 105] :parent 1} ;2
		3 {:keys [12 20 40 91 99] :children [111 112 113 114 115 116] :parent 1} ;3 - overflowed
		4 {:keys [101 107 128 300] :children [121 122 123 124 125] :parent 1} ;4 - full
	})
	ttree
)

(defn createUnbalancedTestTreeWithOverflowedRoot
	"creates example tree for tests"
	[]
	(def ttree { :pageSize 2 :nextId 2 :root 1
		1 {:keys [10 100 1000 5000 12000] :children [101 102 103 104 105 106] :parent nil} ;1
	})
	ttree
)

(defn createUnbalancedTestTreeWithFullBothSiblingsAndFullRoot
	"creates example tree for tests"
	[]
	(def ttree { :pageSize 2 :nextId 7 :root 1
		1 {:keys [10 100 1000 1100] :children [2 3 4 5 6] :parent nil} ;1
		2 {:keys [1 2 3 4] :children [101 102 103 104 105] :parent 1} ;2
		3 {:keys [11 12 13 14 15] :children [111 112 113 114 115 116] :parent 1} ;3 - overflowed
		4 {:keys [121 122 123 124] :children [121 122 123 124 125] :parent 1} ;4 - full
		5 {:keys [1001 1002 1003 ] :children [131 132 133 134 135] :parent 1} ;3 - overflowed
		6 {:keys [1101 1102 ] :children [141 142 143] :parent 1} ;4 - full
	})
	ttree
)

(defn createTestTreeWithEmptyRoot
	"creates example tree for tests"
	[]
	(def ttree { :pageSize 2 :nextId 3 :root 1
		1 {:keys [] :children [2] :parent nil} ;1
		2 {:keys [2 4 7] :children [5 6 7] :parent 1} ;2
	})
	ttree
)

(defn createUnbalancedTestTreeWithOnVergeOfUndeflowBothSiblings
	"creates example tree for tests"
	[]
	(def ttree { :pageSize 2 :nextId 5 :root 1
		1 {:keys [10 100] :children [2 3 4] :parent nil} ;1
		2 {:keys [1 2] :children [101 102 103] :parent 1} ;2
		3 {:keys [50 ] :children [111 112] :parent 1} ;3 - overflowed
		4 {:keys [101 120] :children [121 122 123] :parent 1} ;4 - full
	})
	ttree
)

(defn createUnbalancedTestTreeWithOnVergeOfUndeflowLeftOnlySibling
	"creates example tree for tests"
	[]
	(def ttree { :pageSize 2 :nextId 5 :root 1
		1 {:keys [10 100] :children [2 3 4] :parent nil} ;1
		2 {:keys [1 2] :children [101 102 103] :parent 1} ;2
		3 {:keys [50 75] :children [111 112] :parent 1} ;3 - overflowed
		4 {:keys [101] :children [121 122 123] :parent 1} ;4 - full
	})
	ttree
)

(defn createUnbalancedTestTreeWithOnVergeOfUndeflowRightOnlySibling
	"creates example tree for tests"
	[]
	(def ttree { :pageSize 2 :nextId 5 :root 1
		1 {:keys [10 100] :children [2 3 4] :parent nil} ;1
		2 {:keys [1] :children [101 102 103] :parent 1} ;2
		3 {:keys [50 75] :children [111 112] :parent 1} ;3 - overflowed
		4 {:keys [101 120] :children [121 122 123] :parent 1} ;4 - full
	})
	ttree
)

(defn createUnderflowedTestTreeWithOneKeyInRoot
	"creates example tree for tests"
	[]
	{ :pageSize 2, :root 1, :nextId 4,
		1 {:keys [3], :children [3 2], :parent nil}, 
		2 {:keys [4 5], :children [], :parent 1}, 
		3 {:keys [1], :children [], :parent 1}
	}
)

(defn createUnderflowedTestTreeWithOneKeyInRoot2
	"creates example tree for tests"
	[]
	{ :pageSize 2, :root 3, :nextId 4,
		3 {:keys [3], :children [1 2], :parent nil}, 
		2 {:keys [4], :children [], :parent 3}, 
		1 {:keys [1 2], :children [], :parent 3}
	}
)

(defn create3lvlDeepTestTree
	"creates example tree for tests (with depth = 3)"
	[]	
	{ :root 9, :pageSize 2, :nextId 10,
		1 {:keys [10 40], :children [], :parent 3},
		2 {:keys [210 225 230 240], :children [], :parent 8},
		3 {:keys [60 90], :children [1 7 6], :parent 9},
		4 {:keys [275 280 285 300], :children [], :parent 8},
		5 {:keys [160 170 180 190], :children [], :parent 8},
		6 {:keys [100 110 125 140], :children [], :parent 3},
		7 {:keys [70 80], :children [], :parent 3},
		8 {:keys [200 250], :children [5 2 4], :parent 9},
		9 {:keys [150], :children [3 8], :parent nil}
	}
)

(defn createTestTreeWithWrongParentInChildren
	"creates example tree for tests"
	[]
	(def ttree { :pageSize 2 :nextId 5 :root 1
		1 {:keys [10 100] :children [2 3 4] :parent nil} ;1
		2 {:keys [2 4 7] :children [] :parent 3} ;2
		3 {:keys [12 20 40 91] :children [] :parent 4} ;3
		4 {:keys [101 200] :children [] :parent 2} ;4
	})
	ttree
)

(deftest adjust-test
	(def ttree (createTestTree))
	(def ttree (adjust ttree 2))
	(testing "Tree changed after adjusting a well adjusted page!" (is (= ttree (createTestTree))))

	(def ttree (createTestTree))
	(def ttree (adjust ttree 3)) ; full page
	(testing "Tree changed after adjusting a full page!" (is (= ttree (createTestTree))))
	
	(def ttree (createUnbalancedTestTree))
	(def ttree (adjust ttree 3)) ; overflowed page
	(testing "overflowed tree after adjust not right!" (is (= ttree {1 {:children [2 3 4], :parent nil, :keys [10 99]}, 2 {:children [101 102 103 104], :parent 1, :keys [2 4 7]}, 3 {:children [111 112 113 114 115], :parent 1, :keys [12 20 40 91]}, 4 {:children [116 120 121], :parent 1, :keys [100 101]}, :pageSize 2, :nextId 5, :root 1})))
	
	(def ttree (createUnbalancedTestTreeWithFullRightSibling))
	(def ttree (adjust ttree 3)) ; overflowed page
	(testing "overflowed tree with full right sibling after adjust not right!" (is (= ttree {1 {:children [2 3 4], :parent nil, :keys [12 100]}, 2 {:children [101 102 103 104 111], :parent 1, :keys [2 4 7 10]}, 3 {:children [112 113 114 115 116], :parent 1, :keys [20 40 91 99]}, 4 {:children [120 121 122 123 124 125], :parent 1, :keys [101 107 128 300]}, :pageSize 2, :nextId 5, :root 1})))
	
	(def ttree (createUnbalancedTestTree))
	(def ttree (adjust ttree 4)) ; underflowed page
	(testing "overflowed tree with full right sibling after adjust not right!" (is (= ttree {1 {:keys [10 99], :children [2 3 4], :parent nil},
		2 {:keys [2 4 7], :children [101 102 103 104], :parent 1}, 
		3 {:keys [12 20 40 91], :children [111 112 113 114 115], :parent 1},
		4 {:keys [100 101], :children [116 120 121], :parent 1},
		:root 1, :pageSize 2, :nextId 5}
	)))
	
	(def ttree (createUnbalancedTestTreeWithFullOnlySibling))
	(def ttree (adjust ttree 4)) ; underflowed page
	(testing "overflowed tree with both siblings full after adjust not right!" (is (= ttree{5 {:keys [300 701], :children [], :parent 1}, :pageSize 2, :nextId 6, :root 1, 1 {:children [2 3 4 5], :parent nil, :keys [10 100 128]}, 2 {:keys [2 4 7], :children [], :parent 1}, 3 {:keys [12 20 40 91], :children [], :parent 1}, 4 {:keys [101 107], :children [], :parent 1}})))
	
	(def ttree (createUnbalancedTestTreeWithFullBothSiblings))
	(def ttree (adjust ttree 3)) ; underflowed page
	(testing "overflowed tree with both siblings full after adjust not right!" (is (= ttree { :pageSize 2, :nextId 6, :root 1
		1 {:children [2 3 5 4], :parent nil, :keys [10 40 100]},
		2 {:children [101 102 103 104 105], :parent 1, :keys [2 4 7 9]},
		3 {:keys [12 20], :children [111 112 113], :parent 1},
		4 {:children [121 122 123 124 125], :parent 1, :keys [101 107 128 300]}, 
		5 {:keys [91 99], :children [114 115 116], :parent 1},
	})))
	
	(def ttree (createUnbalancedTestTreeWithOverflowedRoot))
	(def ttree (adjust ttree 1))
	(testing "overflowed tree with overflowed root after adjust not right!" (is (= ttree {:root 3, :pageSize 2, :nextId 4,
		3 {:keys [1000], :children [1 2], :parent nil},
		2 {:keys [5000 12000], :children [104 105 106], :parent 3},
		1 {:keys [10 100], :children [101 102 103], :parent 3}
	})))
	
	(def ttree (createUnbalancedTestTreeWithFullBothSiblingsAndFullRoot))
	(def ttree (adjust ttree 3))
	(testing "overflowed tree with both siblings full and full root after adjust not right!" (is (= ttree {:root 9, :pageSize 2, :nextId 10
		1 {:keys [10 13], :children [2 3 7], :parent 9},
		2 {:children [101 102 103 104 105], :parent 1, :keys [1 2 3 4]},
		3 {:keys [11 12], :children [111 112 113], :parent 1},
		4 {:children [121 122 123 124 125], :parent 8, :keys [121 122 123 124]},
		5 {:children [131 132 133 134 135], :parent 8, :keys [1001 1002 1003]},
		6 {:children [141 142 143], :parent 8, :keys [1101 1102]},
		7 {:keys [14 15], :children [114 115 116], :parent 1},
		8 {:keys [1000 1100], :children [4 5 6], :parent 9},
		9 {:keys [100], :children [1 8], :parent nil}
	})))
	
	(def ttree (createTestTreeWithEmptyRoot))
	(def ttree (adjust ttree 1))
	(testing "underflowed tree with empty root after adjust not right!" (is (= ttree {:pageSize 2, :nextId 3, :root 2, 2 {:children [5 6 7], :parent nil, :keys [2 4 7]}})))
	
	(def ttree (createUnbalancedTestTreeWithOnVergeOfUndeflowBothSiblings))
	(def ttree (adjust ttree 3))
	(testing "underflowed tree with both siblings on verge of underflowing after adjust not right!" (is (= ttree { :root 1, :pageSize 2, :nextId 5
		1 {:children [2 3], :parent nil, :keys [10]},
		2 {:children [101 102 103], :parent 1, :keys [1 2]},
		3 {:keys [50 100 101 120], :children [111 112 121 122 123], :parent 1},
	})))

	(def ttree (createUnbalancedTestTreeWithOnVergeOfUndeflowLeftOnlySibling))
	(def ttree (adjust ttree 4))
	(testing "underflowed tree with only (left) sibling on verge of underflowing after adjust not right!" (is (= ttree { :root 1, :pageSize 2, :nextId 5,
		1 {:keys [10], :children [2 3], :parent nil}, 
		2 {:keys [1 2], :children [101 102 103], :parent 1}, 
		3 {:keys [50 75 100 101], :children [111 112 121 122 123], :parent 1}
	})))
	
	(def ttree (createUnbalancedTestTreeWithOnVergeOfUndeflowRightOnlySibling))
	(def ttree (adjust ttree 2))
	(testing "underflowed tree with only (right) sibling on verge of underflowing after adjust not right!" (is (= ttree { :root 1, :pageSize 2, :nextId 5,
		1 {:keys [100], :children [2 4], :parent nil}, 
		2 {:keys [1 10 50 75], :children [101 102 103 111 112], :parent 1}, 
		4 {:keys [101 120], :children [121 122 123], :parent 1}
	})))
	
	(def ttree (createUnderflowedTestTreeWithOneKeyInRoot))
	(def ttree (adjust ttree 3))
	(testing "underflowed tree with only one key in root after adjust not right!" (is (= ttree {:pageSize 2, :root 3, :nextId 4, 3 {:keys [1 3 4 5], :children [], :parent nil}})))
	
	(def ttree (createUnderflowedTestTreeWithOneKeyInRoot2))
	(def ttree (adjust ttree 2))
	(testing "underflowed tree with only one key in root after adjust not right!" (is (= ttree {:pageSize 2, :root 1, :nextId 4, 1 {:keys [1 2 3 4], :children [], :parent nil}})))
	
	(testing "underflowed tree after adjust not right!" (is (= (adjust {:pageSize 2, :root 3, :nextId 6, 
		4 {:keys [4], :children [], :parent 3}, 
		3 {:children [1 4 2], :parent nil, :keys [2 6]}, 
		2 {:keys [8 9 10 12], :children [], :parent 3}, 
		1 {:keys [-1 0 1], :children [], :parent 3}
	} 4) {:pageSize 2, :root 3, :nextId 6, 4 {:keys [2 4], :children [], :parent 3}, 3 {:children [1 4 2], :parent nil, :keys [1 6]}, 2 {:keys [8 9 10 12], :children [], :parent 3}, 1 {:keys [-1 0], :children [], :parent 3}})))
	
	(testing "underflowed tree after adjust not right!" (is (= (adjust {  :pageSize 2, :root 3, :nextId 6,
		4 {:keys [3 4 5], :children [], :parent 3}, 
		3 {:keys [2 6], :children [1 4 2], :parent nil}, 
		2 {:keys [8 9 10 12], :children [], :parent 3},
		1 {:keys [0], :children [], :parent 3}
	} 1) {:pageSize 2, :root 3, :nextId 6, 4 {:keys [4 5], :children [], :parent 3}, 3 {:children [1 4 2], :parent nil, :keys [3 6]}, 2 {:keys [8 9 10 12], :children [], :parent 3}, 1 {:keys [0 2], :children [], :parent 3}})))
)

(deftest tree-find-test
	(def ttree (createTestTree))
	(def res (tree-find ttree 100))
	(testing "result of find is wrong!" (is (= res [true 1 1])))
	
	(def ttree (createTestTree))
	(def res (tree-find ttree 10))
	(testing "result of find is wrong!" (is (= res [true 1 0])))
	
	(def ttree (createTestTree))
	(def res (tree-find ttree 20))
	(testing "result of find is wrong!" (is (= res [true 3 1])))
	
	(def ttree (createTestTree))
	(def res (tree-find ttree 7))
	(testing "result of find is wrong!" (is (= res [true 2 2])))
	
	(def ttree (createTestTree))
	(def res (tree-find ttree 5))
	(testing "result of find is wrong!" (is (= res [false 2 2])))
)

(deftest tree-add-test
	(def ttree (createTestTree))
	(testing "tree after insert not right!" (is  (= (tree-add ttree 300) {:pageSize 2, :nextId 5, :root 1, 1 {:children [2 3 4], :parent nil, :keys [10 100]}, 2 {:keys [2 4 7], :children [], :parent 1}, 3 {:keys [12 20 40 91], :children [], :parent 1}, 4 {:keys [101 200 300], :children [], :parent 1}})))
	
	(def ttree (createTestTree))
	(testing "tree after insert not right!" (is  (= (tree-add ttree 5) {:pageSize 2, :nextId 5, :root 1, 1 {:children [2 3 4], :parent nil, :keys [10 100]}, 2 {:keys [2 4 5 7], :children [], :parent 1}, 3 {:keys [12 20 40 91], :children [], :parent 1}, 4 {:keys [101 200], :children [], :parent 1}})))
	
	(def ttree (createTestTree))
	(testing "tree after insert not right!" (is  (= (tree-add ttree 50) {:pageSize 2, :nextId 5, :root 1, 1 {:children [2 3 4], :parent nil, :keys [10 91]}, 2 {:keys [2 4 7], :children [], :parent 1}, 3 {:keys [12 20 40 50], :children [], :parent 1}, 4 {:keys [100 101 200], :children [], :parent 1}})))
)

(deftest tree-remove-test
	(def ttree (createTestTree))	
	(testing "tree after remove not right!" (is  (= (tree-remove ttree 91) {:pageSize 2, :nextId 5, :root 1, 1 {:children [2 3 4], :parent nil, :keys [10 100]}, 2 {:keys [2 4 7], :children [], :parent 1}, 3 {:keys [12 20 40], :children [], :parent 1}, 4 {:keys [101 200], :children [], :parent 1}})))

	(def ttree (createTestTree))
	(testing "tree after remove not right!" (is  (= (tree-remove ttree 101) {:pageSize 2, :nextId 5, :root 1, 1 {:children [2 3 4], :parent nil, :keys [10 91]}, 2 {:keys [2 4 7], :children [], :parent 1}, 3 {:keys [12 20 40], :children [], :parent 1}, 4 {:keys [100 200], :children [], :parent 1}})))
	
	(def ttree (createTestTree))
	(testing "tree after remove not right!" (is  (= (tree-remove ttree 10) {:pageSize 2, :nextId 5, :root 1, 1 {:children [2 3 4], :parent nil, :keys [12 100]}, 2 {:keys [2 4 7], :children [], :parent 1}, 3 {:keys [20 40 91], :children [], :parent 1}, 4 {:keys [101 200], :children [], :parent 1}})))	
	
	(def ttree (createTestTree))
	(testing "tree after remove not right!" (is  (= (tree-remove ttree 100) {:pageSize 2, :nextId 5, :root 1, 1 {:children [2 3 4], :parent nil, :keys [10 91]}, 2 {:keys [2 4 7], :children [], :parent 1}, 3 {:keys [12 20 40], :children [], :parent 1}, 4 {:keys [101 200], :children [], :parent 1}})))	
	
	(def ttree (create3lvlDeepTestTree))
	(testing "tree after remove not right!" (is  (= (tree-remove ttree 90) { :root 9, :pageSize 2, :nextId 10
		1 {:keys [10 40], :children [], :parent 3},
		2 {:keys [210 225 230 240], :children [], :parent 8},
		3 {:keys [60 100], :children [1 7 6], :parent 9},
		4 {:keys [275 280 285 300], :children [], :parent 8},
		5 {:keys [160 170 180 190], :children [], :parent 8},
		6 {:keys [110 125 140], :children [], :parent 3},
		7 {:keys [70 80], :children [], :parent 3},
		8 {:keys [200 250], :children [5 2 4], :parent 9},
		9 {:keys [150], :children [3 8], :parent nil},
	})))

	(def ttree (create3lvlDeepTestTree))
	(testing "tree after remove not right!" (is  (= (tree-remove ttree 150) { :root 9, :pageSize 2, :nextId 10
		1 {:keys [10 40], :children [], :parent 3},
		2 {:keys [210 225 230 240], :children [], :parent 8},
		3 {:keys [60 90], :children [1 7 6], :parent 9},
		4 {:keys [275 280 285 300], :children [], :parent 8},
		5 {:keys [170 180 190], :children [], :parent 8},
		6 {:keys [100 110 125 140], :children [], :parent 3},
		7 {:keys [70 80], :children [], :parent 3},
		8 {:keys [200 250], :children [5 2 4], :parent 9},
		9 {:keys [160], :children [3 8], :parent nil}
	})))
	
	(testing "tree after remove not right!" (is (= (tree-remove { :pageSize 2, :root 3, :nextId 6,
		4 {:keys [3 4 5], :children [], :parent 3}, 
		3 {:keys [2 6], :children [1 4 2], :parent nil}, 
		2 {:keys [8 9 10 12], :children [], :parent 3},
		1 {:keys [0 1], :children [], :parent 3}
	} 1) {:pageSize 2, :root 3, :nextId 6, 4 {:keys [4 5], :children [], :parent 3}, 3 {:children [1 4 2], :parent nil, :keys [3 6]}, 2 {:keys [8 9 10 12], :children [], :parent 3}, 1 {:keys [0 2], :children [], :parent 3}})))
)

(deftest tree-create-test
	(def ttree (tree-create 2 9 1 13 100 21 9 14 8 1 7 2 5 6 7))
	(testing "newly created tree is wrong!" (is (= ttree { :pageSize 2, :root 3, :nextId 5,
		4 {:keys [6 7 8], :children [], :parent 3}, 
		3 {:keys [5 9], :children [1 4 2], :parent nil}, 
		2 {:keys [13 14 21 100], :children [], :parent 3}, 
		1 {:keys [1 2], :children [], :parent 3}
	})))
)

(deftest tree-size-test
  (def ttree (tree-create 2 9 1 13 100 21 9 14 8 1 7 2 5 6 7))
  (def tsize (tree-size ttree))
  (testing "number of keys in tree is wrong!" (is (= tsize 11)))
)

(deftest tree-json-test
    (def ttree (tree-create 2 9 1 13 100 21 9 14 8 1 7 2 5 6 7))

    (def m (hash-map 'tree (vec [(hash-map 'node (hash-map 'id 3 'key [5 9] 'ptr [1 4 2] 'level 1)),
                                 (hash-map 'node (hash-map 'id 1 'key [1 2] 'ptr [] 'level 2)),
                                 (hash-map 'node (hash-map 'id 4 'key [6 7 8] 'ptr [] 'level 2)),
                                 (hash-map 'node (hash-map 'id 2 'key [13 14 21 100] 'ptr [] 'level 2))]
                               )))

    (def tjson (tree-json ttree))
    (testing (is (= tjson "{\n\"tree\":\n\t[\n\t{\"node\":{\"keys\":[5,9],\"id\":3,\"children\":[1,4,2],\"level\":1}},\n\t{\"node\":{\"keys\":[1,2],\"id\":1,\"children\":[],\"level\":2}},\n\t{\"node\":{\"keys\":[6,7,8],\"id\":4,\"children\":[],\"level\":2}},\n\t{\"node\":{\"keys\":[13,14,21,100],\"id\":2,\"children\":[],\"level\":2}}\n\t]\n}")))
)

(deftest updateParentInChildren-test
	(testing "tree after children update is wrong!" (is (= (updateParentInChildren (createTestTreeWithWrongParentInChildren) 1) (createTestTree))))
)
